package QuestionDaily;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class maximumSumQueries_2736 {
    /**
     * 对于第 i 个查询，在所有下标 j (0 <= j < n)中
     * 找到满足 nums1[j] >= xi 且 nums2[j] >= yi 的位置
     * 找出 nums1[j] + nums2[j] 的 最大值 ，如果不存在满足条件的 j 则返回 -1 。
     * @param nums1 下标从 0 开始的整数数组
     * @param nums2 1 <= nums1[i], nums2[i] <= 109
     * @param queries 下标从 1 开始的二维数组，其中 queries[i] = [xi, yi] 。
     * @return 数组answer ，其中 answer[i] 是第 i 个查询的答案。
     */
    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        /**
         * 暴力遍历超时
         */
        int []answer=new int[queries.length];
        for(int i=0;i<queries.length;i++){
            int maxSum=-1;
            for(int j=0;j< nums1.length;j++){
                if(nums1[j]>=queries[i][0]&&nums2[j]>=queries[i][1]){
                    maxSum=Integer.max(maxSum,nums1[j]+nums2[j]);
                }
            }
            answer[i]=maxSum;
        }
        return answer;
    }

    public int[] maximumSumQueries2(int[] nums1, int[] nums2, int[][] queries) {
        /**
         * 想法
         * 1，维护两个指针,无用，因为遍历次数并没有变化
         * 2，维护一个10*10的数组，降序存储所有可能的数字组合,不行，发现数字位数不是一位数
         * 3，看官解，思路是，对nums1和nums2的组合和queries分别以第一位优先，进行降序排序
         * 然后使用单调栈分情况处理
         */
        int n = nums1.length;
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = nums1[i];
            a[i][1] = nums2[i];
        }
        Arrays.sort(a, (x, y) -> y[0] - x[0] );     //对nums1和nums2的组合依照第一个元素进行降序处理

        Integer[] qid = new Integer[queries.length];
        for (int i = 0; i < queries.length; i++) {
            qid[i] = i;
        }
        Arrays.sort(qid, (i, j) -> queries[j][0] - queries[i][0]);  //依照queries的第一个元素进行降序处理

        int[] ans = new int[queries.length];
        List<int[]> st = new ArrayList<>(); //存储的是nums2[j]的值和组合的值，按nums2[j]的值单调递增，组合值单调递减的单调栈
        int j = 0;
        for (int i : qid) {
            int x = queries[i][0], y = queries[i][1];
            for (; j < n && a[j][0] >= x; j++) { //a[j][0]已经是降序，遇到第一个不大于x的即可退出
                // 把重心放在 nums2[j] 与 y上 。下面只需关心 a[j][1]
                while (!st.isEmpty() && st.get(st.size() - 1)[1] <= a[j][0] + a[j][1]) { //如果单调栈顶的组合值小于等于新的组合值，去掉栈顶元素，确保组合值递减
                    st.remove(st.size() - 1);
                }
                //如果nums2[j]小于等于之前遍历的nums2[j], 因为nums1[j]已经是递减，此时组合值只会更小，不予考虑
                //如果nums2[j]大于之前遍历的nums2[j],添加进单调栈中
                if (st.isEmpty() || st.get(st.size() - 1)[0] < a[j][1]) {
                    st.add(new int[]{a[j][1], a[j][0] + a[j][1]});
                }
            }
            //找到最大值的下标
            int p = lowerBound(st, y);
            ans[i] = p < st.size() ? st.get(p)[1] : -1;
        }
        return ans;
    }

    private int lowerBound(List<int[]> st, int target) {
        int left = -1, right = st.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            int mid = (left + right) >>> 1;
            if (st.get(mid)[0] >= target) {
                right = mid; // 范围缩小到 (left, mid)
            } else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        return right;
    }
}
